package com.honeywen.mymvc.opera;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * https://leetcode-cn.com/contest/weekly-contest-118/problems/powerful-integers/
 *
 * @author wangwei
 * @date 2019/8/15
 */
public class Test {

    /**
     * 0 0
     * 1 0
     * 1 1
     * 2 0
     * 2 1
     * 2 2
     * 3 0
     * 3 1
     * 3 2
     * 3 3
     *
     * @param x
     * @param y
     * @param bound
     * @return
     */


    public static List<Integer> powerfulIntegers3(int x, int y, int bound) {
        List<Integer> list = new ArrayList<>();

        if (bound < 2) {
            return list;
        }
        if (bound == 2 || (x == 1 && y == 1)) {
            list.add(2);
            return list;
        }

        int left = 0, right = 0;


        while (true) {

            int min = Math.min(x, y);
            min = min >= 2 ? min : 2;
            if (Math.pow(min, right) > bound){
                break;
            }


            if (left == right) {
                int a = (int)Math.pow(x, left);
                int b = (int)Math.pow(y, right);

                if (a + b <= bound) {
                    list.add(a + b);
                }

                left++;
                right = 0;
            }

            int a = (int) Math.pow(x, left);
            int b = (int) Math.pow(y, right);
            if (a + b <= bound) {
                list.add(a + b);
            }

            a = (int) Math.pow(x, right);
            b = (int) Math.pow(y, left);
            if (a + b <= bound) {
                list.add(a + b);
            }
            right++;

        }



        return new ArrayList<>(new HashSet<>(list));

    }



    public static void main(String[] args) {

        System.out.println(powerfulIntegers3(2, 1, 10));
//        System.out.println(powerfulIntegers3(2, 4, 12));
//        System.out.println(powerfulIntegers2(2, 3, 10));
//        System.out.println(powerfulIntegers2(3, 5, 15));
//        System.out.println(powerfulIntegers2(1, 1, 1));
//        System.out.println(powerfulIntegers2(1, 1, 3));


    }
}
